#ifndef __QUICKITERATIVE_CPP__
#define __QUICKITERATIVE_CPP__

#include "QuickIterative.h"
#include "QuicksortItemType.h"

template <class T>
void QuickSortIter(T arr[], int left , int right)
{
	if (left > right)
		throw "Left must be smaller than right!!!";

	stack<QuicksortItemType> st; // the stack that will contain the recursive iterations
	st.makeEmpty();
	ItemType<QuicksortItemType> curr, next; // every ItemType will contain the iteration's data
	int pivot;
	curr.getData().set(left, right, START); // initialize the first iteration for the current item
	st.push(curr);

	// as long as there are recursive iterations in the stack,
	// keep the loop going
	while (!st.isEmpty())
	{
		curr = st.pop(); // pop the latest recursive iteration from the stack
		left = curr.getData().getLeft();
		right = curr.getData().getRight();
		if ( left < right )
		{
			// make the partition
			// and push first ItemType (curr) for preperation to the right part of the array,
			// and push second ItemType (next) to deal with the left part of the array
			if (curr.getData().getLine() == START)
			{
				pivot = Partition<T>(arr, left, right); // returns the correct index of the pivot and arrange the other items accordingly
				curr.getData().setIndex(pivot);
				curr.getData().setLine(AFTER_FIRST);
				st.push(curr);
				// deal with the left part of the array except the pivot
				next.getData().set(left, pivot-1, START);
				st.push(next);
			}
		
			else if (curr.getData().getLine() == AFTER_FIRST)
			{
				// deal with the right part of the array except the pivot
				int theIndex = curr.getData().getIndex();
				next.getData().set(theIndex + 1, right, START);
				st.push(next);
			}
		}
	}
}

#endif